class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

# 自下而上的定义二叉树 [3,9,20,3,4,15,7]
# ltree = TreeNode(9)
# ltree.left = TreeNode(3)
# ltree.right = TreeNode(4)
#
# rtree = TreeNode(20)
# rtree.left = TreeNode(15)
# rtree.right = TreeNode(7)
#
# root = TreeNode(3)
# root.left = ltree
# root.right = rtree


# 通过递归来构建二叉树
def buildTree(nums):
    def build(idx):
        # base case
        if idx >= len(nums): return None
        if nums[idx] is None: return None

        root = TreeNode(nums[idx])

        root.left = build(2*idx+1)
        root.right = build(2*idx+2)

        return root

    return build(0)

L = [3, 9, 20, None, None, 15, 7]
root = buildTree(L)
print("当前二叉树: {}".format(L))
print(root.right.right.val)

# 遍历二叉树
def traverse(root):
    if root is None: return
    # 前序位置
    print("前序遍历—当前节点值：{}".format(root.val))
    traverse(root.left)
    traverse(root.right)
    # print("后序遍历—当前节点值: {}".format(root.val))
traverse(root)

# 统计二叉树左右子树各有多少个节点
def cntLRNode(root):
    if root is None: return 0
    l = cntLRNode(root.left)
    r = cntLRNode(root.right)
    print("当前节点{}的左子树个数{}, 右子树个数{}".format(root.val, l, r))
    return l + r + 1
cntLRNode(root)

# L104求二叉树最大深度
# 左子树最大深度+右子树最大深度
def maxDepth(root):
    if root is None: return 0
    return max(maxDepth(root.left), maxDepth(root.right)) + 1

print("二叉树{}的最大深度为:{}".format(L, maxDepth(root)))


# L543求二叉树的直径=左右节点的最大深度和
res = 0
def diameterOfBinTree(root):
    def maxDepth(root):
        if root is None: return 0

        lmax = maxDepth(root.left)
        rmax = maxDepth(root.right)
        # 后序位置：计算直径
        global res
        res = max(lmax+rmax, res)

        return max(lmax, rmax) + 1

    maxDepth(root)
    return res

print("二叉树{}的直径为:{}".format(L, diameterOfBinTree(root)))

# L116 填充每个节点的下一个右侧指针
def connect(root):
    if root is None: return root

    def connectTwoNode(node1, node2):
        if not node1 or not node2: return

        node1.next = node2

        connectTwoNode(node1.left, node1.right)
        connectTwoNode(node2.left, node2.right)
        connectTwoNode(node1.right, node2.left)

    connectTwoNode(root.left, root.right)

